/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX(a,b) (a > b ? a : b)  // 宏定义：获取两个值中较大的一个

typedef struct TreeNode TreeNode;

int isNot;  // 全局标志变量：一旦检测到不平衡，则置为1，用于提前终止递归

// step 1# 递归获取当前子树的高度，同时检查是否平衡
int getHeight(TreeNode *node) {
    if (isNot) return -1;             // 如果已发现不平衡，直接返回-1，提前结束递归
    if (node == NULL) return 0;       // 空节点高度为0

    // step 2# 递归计算左子树高度
    int leftHeight = getHeight(node->left);
    if (leftHeight == -1) {           // 如果左子树已标记为不平衡，提前返回
        isNot = 1;
        return -1;
    }

    // step 3# 递归计算右子树高度
    int rightHeight = getHeight(node->right);
    if (rightHeight == -1) {          // 如果右子树已标记为不平衡，提前返回
        isNot = 1;
        return -1;
    }

    // step 4# 检查当前节点是否平衡：左右高度差超过1则为不平衡
    if (abs(leftHeight - rightHeight) > 1) {
        return -1;  // 当前子树不平衡
    }

    // step 5# 返回当前节点的高度（较高子树高度 + 1）
    int curHeight = MAX(leftHeight, rightHeight) + 1;
    return curHeight;
}

// step 6# 判断整棵树是否为平衡二叉树
bool isBalanced(struct TreeNode* root) {
    isNot = 0;                      // 初始化不平衡标志
    return getHeight(root) == -1 ? false : true;  // 若根节点返回 -1，说明树不平衡
}
